/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-12
 * Time:9:20
 */
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
 class Solution {

         public boolean chkPalindrome2(ListNode A) {
         ListNode B=null;
         ListNode cur=A;
         while(cur!=null){
             ListNode node=new ListNode(cur.val);
             node.next=B;
             B=node;
             cur=cur.next;
         }
         while(A.val==B.val){
             A=A.next;
             B=B.next;
             if(A==null){
                 return true;
             }
         }
         return false;
     }
         public boolean chkPalindrome1(ListNode A) {
         // write code here
         ListNode fast=A;
         ListNode slow=A;
         while(fast.next!=null&&fast.next.next!=null){
             fast=fast.next.next;
             slow=slow.next;
         }
         ListNode isSlow=slow;
         //逆置后半部分
         ListNode cur=slow.next;
         ListNode curnext=cur.next;
         if(fast.next!=null){
             //是偶数
             while(curnext!=null){
                 slow=cur;
                 cur=curnext;
                 curnext=curnext.next;
                 cur.next=slow;
             }
             while(A.next!=isSlow){
                 if(A.val!=cur.val){
                     return false;
                 }
                 A=A.next;
                 cur=cur.next;
             }
             if(A.val== cur.val){
                 return true;
             }else {
                 return false;
             }
         }else {
             //奇数
             while(curnext!=null){
                 cur.next=slow;
                 slow=cur;
                 cur=curnext;
                 curnext=curnext.next;
             }
             cur.next=slow;
             while (A!=cur){
                 if(A.val!=cur.val){
                     return false;
                 }
                 A=A.next;
                 cur=cur.next;
             }
             return true;
         }
     }
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         ListNode list1=headA;
         ListNode list2=headB;
         int size1=0;
         int size2=0;
         while(list1!=null){
             size1++;
             list1=list1.next;
         }
         while(list2!=null){
             size2++;
             list2=list2.next;
         }
         list1=headA;
         list2=headB;
         if(size1>size2){
             for (int i = 0; i < size1-size2; i++) {
                 list1=list1.next;
             }
             while(list1!=null){
                 if(list1==list2){
                     return list1;
                 }
                 list1=list1.next;
                 list2=list2.next;
             }
         }else{
             for (int i = 0; i < size2-size1; i++) {
                 list1=list1.next;
             }
             while(list1!=null){
                 if(list1==list2){
                     return list1;
                 }
                 list1=list1.next;
                 list2=list2.next;
             }
         }
         return null;
     }
     public boolean hasCycle(ListNode head) {
         if(head==null){
             return false;
         }
         ListNode fast=head;
         ListNode slow=head;
         while(fast!=null&&fast.next!=null){
             if(fast.next==slow||fast.next.next==slow){
                 return true;
             }
             fast=fast.next.next;
             slow=slow.next;
         }
         return false;
     }
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            if(fast.next==slow){
                break;
            }
            if(fast.next.next==slow){
                break;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        if(fast.next==null||fast.next.next==null){
            return null;
        }
        fast=head;
        while(fast==slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
    }
}
public class Test {
}
